package com.leetcode;

import java.util.ArrayDeque;

import org.testng.annotations.Test;

public class SurroundedRegions {
	private int M;
	private int N;
	private char[][] b;
	ArrayDeque<Point> queue;
	
	public void solve(char[][] board) {
        M = board.length;
        N = M==0? 0 : board[0].length;
        b = board;
        queue = new ArrayDeque<Point>();
        for (int i=0; i<M; i++) {
        	if (board[i][0] == 'O') mark(i, 0);
        	if (board[i][N-1] == 'O') mark(i, N-1);
        }
        for (int i=0; i<N; i++) {
        	if (board[0][i] == 'O') mark(0, i);
        	if (board[M-1][i] == 'O') mark(M-1, i);
        }
        
        while (!queue.isEmpty()) {
        	Point p = queue.remove();
        	add(p.x-1, p.y);
        	add(p.x+1, p.y);
        	add(p.x, p.y-1);
        	add(p.x, p.y+1);
        }
        
        for (int i=0; i<M; i++) {
        	for (int j=0; j<N; j++) {
        		if (b[i][j] == 'O') b[i][j] = 'X';
        		if (b[i][j] == 'Y') b[i][j] = 'O';
        	}
        }
    }
	
	private void mark(int x, int y) {
		queue.add(new Point(x, y));
		b[x][y] = 'Y';
	}
	
	private void add(int x, int y) {
		if (x>=0 && x<M && y>=0 && y<N && b[x][y]=='O') {
			mark(x, y);
		}
	}
	
	private class Point {
		int x;
		int y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	@Test
	public void test1() {
		char[][] b = new char[][]{
				{'X', 'X', 'X', 'X'},
				{'X', 'O', 'O', 'X'},
				{'X', 'X', 'O', 'X'},
				{'X', 'O', 'X', 'X'}
		};
		new SurroundedRegions().solve(b);
	}
}